#include <iostream>
#include <assert.h>
#include <algorithm>
#include <string.h>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;

// namespace sl
//{
// template<class T>
// class vector
//{
// public:
//
//   //vector和string 的迭代器都是原生指针
//   typedef T* iterator;
//   typedef const T* const_iterator;
//
//   vector()
//     :_start(nullptr)
//      ,_finish(nullptr)
//      ,_endOfStorage(nullptr)
//   {}
//
//   //如果实现了下方的迭代器区间构造，那么下面这样写会有一点小bug
//   //为什么这样说呢？你看看如果按照这样去构造一个对象会出现什么问题
//   //vector<int> v(10, 2);这个时候因为构造函数的第一个参数是size_t，所以编译器默认认为此时调用迭代器区间构造更合适
//   //那么此时如何修改就一目了然了
//   //vector(size_t n, const T& val = T())
//   //  :_start(nullptr)
//   //   ,_finish(nullptr)
//   //   ,_endOfStorage(nullptr)
//   //{
//   //  reserve(n);
//
//   //  for(size_t i = 0; i < n; i++)
//   //  {
//   //    push_back(val);
//   //  }
//   //}
//
//   vector(int n, const T& val = T())
//     :_start(nullptr)
//      ,_finish(nullptr)
//      ,_endOfStorage(nullptr)
//   {
//     reserve(n);
//
//     for(int i = 0; i < n; i++)
//     {
//       push_back(val);
//     }
//   }
//
//
//
//   template<class InputIterator>
//   vector(InputIterator first, InputIterator last)
//     :_start(nullptr)
//      ,_finish(nullptr)
//      ,_endOfStorage(nullptr)
//   {
//     while(first != last)
//     {
//       push_back(*first);
//       first++;
//     }
//   }
//
//
//   void swap(vector<T>& v)
//   {
//     std::swap(_start, v._start);
//     std::swap(_finish, v._finish);
//     std::swap(_endOfStorage, v._endOfStorage);
//   }
//
//   vector(const vector<T>& v)
//     :_start(nullptr)
//      ,_finish(nullptr)
//      ,_endOfStorage(nullptr)
//   {
//     vector<T> tmp(v.begin(), v.end());
//     swap(tmp);
//   }
//
//   //v1 = v2;
//   vector<T>& operator=(vector<T> v)
//   {
//     swap(v);
//     return *this;
//   }
//
//
//   ~vector()
//   {
//     if(_start)
//     {
//       delete[] _start;
//       _start = nullptr;
//       _finish = nullptr;
//       _endOfStorage = nullptr;
//     }
//   }
//
//   iterator begin()
//   {
//     return _start;
//   }
//
//   iterator end()
//   {
//     return _finish;
//   }
//
//   const_iterator begin()const
//   {
//     return _start;
//   }
//
//   const_iterator end()const
//   {
//     return _finish;
//   }
//
//   size_t size()const
//   {
//     return _finish - _start;
//   }
//
//   size_t capacity()const
//   {
//     return _endOfStorage - _start;
//   }
//
//   T& operator[](size_t pos)
//   {
//     assert(pos < size());
//
//     return _start[pos];
//   }
//
//   const T& operator[](size_t pos)const
//   {
//     assert(pos < size());
//
//     return _start[pos];
//   }
//
//   ////这种写法有bug
//   //void reserve(size_t n)
//   //{
//   //  if(n > capacity())
//   //  {
//   //    char* tmp = new T[n];
//   //    if(_start)
//   //    {
//   //      memcpy(tmp, _start, size() * sizeof(T));
//   //      delete[] _start;
//   //    }
//   //    _start = tmp;
//   //    _finish = _start + size();//size()=>_finish - _start;  _start已经变化了
//   //    _endOfStorage = _start + capacity();//capacity()=>_endOfStorage - _start;//  _start已经变化了
//   //  }
//   //}
//
//   //正确方法
//   void reserve(size_t n)
//   {
//     if(n > capacity())
//     {
//      size_t sz = size();
//      T* tmp = new T[n];
//      if(_start)
//      {
//        memcpy(tmp, _start, size() * sizeof(T));
//        delete[] _start;
//      }
//      _start = tmp;
//      _finish = _start + sz;
//      _endOfStorage = _start + n;
//     }
//   }
//
//
//   //void resize(size_t n, T val = T()){
//   //  if(n < size()){
//   //    _finish = _start + n;
//   //  }
//   //  else{
//   //    if(n > capacity()){
//   //      reserve(n);
//   //    }
//   //    else{
//   //      while(_finish < _start + n){
//   //        *_finish = val;
//   //        _finish++;
//   //      }
//   //    }
//   //  }
//   //}
//   //
//
//   void resize(size_t n, const T& val = T())
//   {
//     if(n > capacity())
//     {
//       reserve(n);
//     }
//     if(n > size())
//     {
//       while(_finish < _start + n)
//       {
//         *_finish = val;
//         _finish++;
//       }
//     }else{
//       _finish = _start + n;
//     }
//   }
//
//
//   void push_back(const T& x)
//   {
//     if(_finish == _endOfStorage)
//     {
//       size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
//       reserve(newCapacity);
//     }
//     *_finish = x;
//     _finish++;
//   }
//
//   void pop_back()
//   {
//     if(_finish > _start)
//     {
//       _finish--;
//     }
//   }
//
//
//   //有bug，扩容之后，_start就变化了
//   //void insert(iterator pos, const T& x)
//   //{
//   //  assert(pos >= _start && pos <= _finish);
//
//   //  if(_finish == _endOfStorage)
//   //  {
//   //    size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
//   //    reserve(newCapacity);
//   //  }
//
//   //  iterator end = _finish - 1;
//   //  while(end >= pos)
//   //  {
//   //    *(_end + 1) = *end;
//   //    end--;
//   //  }
//   //  *pos = x;
//   //  _finish++;
//   //}
//
//
//   iterator insert(iterator pos, const T& x)
//   {
//     assert(pos >= _start && pos <= _finish);
//
//     //扩容之后，_start就变化了，所以要一开始计算出pos相对于_start的距离
//     //否则会有迭代器失效——野指针引起的
//     if(_finish == _endOfStorage)
//     {
//       size_t n = pos - _start;
//       size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
//       reserve(newCapacity);
//       pos = _start + n;
//     }
//
//     iterator end = _finish - 1;
//     while(end >= pos)
//     {
//       *(end + 1) = *end;
//       end--;
//     }
//     *pos = x;
//     _finish++;
//
//     //如果不提供返回值的话，可能会导致迭代器指向位置意义变了
//     return pos;
//   }
//
//   //正常情况下erase()不会导致缩容，所以不用考虑野指针的情况
//   //但是可能因为迭代器指向位置变了导致迭代器失效
//   iterator erase(iterator pos)
//   {
//     iterator begin = pos + 1;
//     while(begin != _finish)
//     {
//       *(begin - 1) = *begin;
//       begin++;
//     }
//
//     _finish--;
//     return pos;//故而提供返回值以便调用函数时接收
//   }
//
// private:
//   iterator _start;//指向数据空间的开始
//   iterator _finish;//指向有效数据的尾
//   iterator _endOfStorage;//指向存储容量的尾
// };
// }
//
//
// void test1()
//{
//   sl::vector<int> v;
//   for(int i = 1; i <= 4; i++)
//   {
//     v.push_back(i);
//   }
//   sl::vector<int>::iterator it = v.begin();
//   while(it != v.end())
//   {
//     if(*it % 2 == 0)
//     {
//       it = v.insert(it, 20);
//       it++;
//     }
//     it++;
//   }
//
//   for(auto& e : v)
//   {
//     cout << e << " ";
//   }
// }

// namespace sl
// {
//   template<class T>
//   class vector
//   {
//   public:
//     typedef T* iterator;
//     typedef const T* const_iterator;

//     size_t size() const
//     {
//       return _finish - _start;
//     }

//     size_t capacity() const
//     {
//       return _endOfStorage - _start;
//     }

//     iterator begin() const
//     {
//       return _start;
//     }

//     iterator end() const
//     {
//       return _finish;
//     }

//     T& operator[](size_t pos)
//     {
//       assert(pos >= 0 && pos < size());
//       return _start[pos];
//     }

//     const T& operator[](size_t pos) const
//     {
//       assert(pos >= 0 && pos < size());
//       return _start[pos];
//     }

//     void reserve(size_t n)
//     {
//       if(n > capacity())
//       {
//         size_t sz = size();//size():_finish-_start;
//         //所以一开始需要将size()的值保存起来
//         T* tmp = new T[n];
//         if(_start)
//         {
//           memcpy(tmp, _start, size() * sizeof(T));
//           delete[] _start;
//         }
//         _start = tmp;
//         _finish = _start + sz;
//         _endOfStorage = _start + n;
//       }
//     }

//     void resize(size_t n, const T& val = T())
//     {
//       if(n > capacity())
//       {
//         reserve(n);
//       }
//       if(n > size())
//       {
//         while(_finish < _start + n)
//         {
//           *_finish = val;
//           _finish++;
//         }
//       }else{
//         _finish = _start + n;
//       }
//     }

//     void push_back(const T& val)
//     {
//       if(_finish == _endOfStorage)
//       {
//         size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
//         reserve(newCapacity);
//       }
//       *_finish = val;
//       _finish++;
//     }

//   private:
//     iterator _start;
//     iterator _finish;
//     iterator _endOfStorage;
//   }
// }

// void test2()
// {

// }

// int main()
// {
//   //test1();

//   test2();
//   return 0;
// }

// namespace sl
// {
//   template<class T>
//   class vector
//   {
//   public:
//     typedef T* iterator;
//     typedef const T* const_iterator;

//     vector()
//       :_start(nullptr)
//       ,_finish(nullptr)
//       ,_endOfStroage(nullptr)
//     {}

//     ~vector()
//     {
//       if(_start)
//       {
//         delete[] _str;
//         _start = nullptr;
//         _finish = nullptr;
//         _endOfStorage = nullptr;
//       }
//     }

//     //迭代器区间构造
//     template<class InputIterator>
//     vector(InputIterator first, InputIterator last)
//     {

//     }

//     void swap()

//     //拷贝构造
//     //vector<int> v2(v1);
//     vector(const vector<T>& v)
//     {

//     }

//     iterator begin()
//     {
//       return _start;
//     }

//     const_iterator begin()const
//     {
//       return _start;
//     }

//     iterator end()
//     {
//       return _finish;
//     }

//     const_iterator end()const
//     {
//       return _finish;
//     }

//     size_t size()const
//     {
//       return _finish - _start;
//     }

//     size_t capacity()const
//     {
//       return _endOfStorage - _start;
//     }

//   private:
//     iterator _start;
//     iterator _finish;
//     iterator _endOfStorage;
//   };
// }

// namespace sl
// {
//     template<class T>
//     class vector
//     {
//         typedef T* iterator;
//         typedef const T* const_iterator;

//     public:
//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         ~vector()
//         {
//             if(_start)
//             {
//                 delete[] _start;
//                 _start = _finish = _endOfStorage = nullptr;
//             }
//         }

//         //迭代器区间构造
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         vector(int n, const T& val = T())
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             reserve(n);
//             for(int i = 0; i < n; i++)
//             {
//                 push_back(val);
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T>& operator=(vector<int> v)
//         {
//             swap(v);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin()const
//         {
//             return _start;
//         }

//         const_iterator end()const
//         {
//             return _finish;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             if(n > capacity())//_endOfStorage - _start;
//             {
//                 size_t sz = size();//_finish - _start;
//                 T* tmp = new T[n];

//                 if(_start)
//                 {
//                     for(size_t i = 0; i < sz; i++)
//                     {
//                         tmp[i] = _start[i];
//                     }
//                 }

//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }

//         }

//         void resize(size_t n, const T val = T())
//         {
//             if(n < size())
//             {
//                 _finish = _start + n;
//             }
//             else
//             {
//                 if(n > capacity())
//                 {
//                     reserve(n);
//                 }
//                 for(size_t i = size(); i < n; i++)
//                 {
//                     _start[i] = val;
//                 }
//             }
//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }

//             *_finish = x;
//             _finish++;
//         }

//         void display()const
//         {
//             const_iterator first = begin();
//             while(first != end())
//             {
//                 cout << *first << " ";
//                 first++;
//             }
//             cout << endl;
//         }
//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;

//     };
// }

// namespace sl
// {
//     template<class T>
//     class vector
//     {
//     public:
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         //迭代器区间构造
//         //重新声明迭代器,可以使迭代器区间使用任意的迭代器
//         //string s("hello");
//         //vector<int> v(s.begin(), s.end());
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         ~vector()
//         {
//             if(_start)
//             {
//                 delete[] _start;
//                 _start = _finish = _endOfStorage = nullptr;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,endOgStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T>& operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin()const
//         {
//             return _start;
//         }

//         const_iterator end()const
//         {
//             return _finish;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             if(n > capacity())
//             {
//                 T* tmp = new T[n];
//                 size_t sz = size();
//                 if(_start)
//                 {
//                     for(size_t i = 0; i < sz; i++)
//                     {
//                         tmp[i] = _start[i];
//                     }
//                 }

//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }
//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }
//             *_finish = x;
//             _finish++;
//         }

//         void display()
//         {
//             iterator it = begin();
//             while(it != end())
//             {
//                 cout << *it << " ";
//                 it++;
//             }
//             cout << endl;
//         }
//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
//     };
// }

// namespace sl
// {
//     template<class T>
//     class vector
//     {
//     public:
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         ~vector()
//         {
//             if(_start)
//             {
//                 delete[] _start;
//                 _start = _finish = _endOfStorage = nullptr;
//             }
//         }

//         //迭代器区间构造
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T>& operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin()const
//         {
//             return _start;
//         }

//         const_iterator end()const
//         {
//             return _finish;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             if(n > capacity())
//             {
//                 T* tmp = new T[n];
//                 size_t sz = size();

//                 for(size_t i = 0; i < sz; i++)
//                 {
//                     tmp[i] = _start[i];
//                 }

//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }

//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }

//             *_finish = x;
//             _finish++;
//         }

//         void display()
//         {
//             iterator it = begin();
//             while(it != end())
//             {
//                 cout << *it << " ";
//                 it++;
//             }
//             cout << endl;
//         }

//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
// //     };
// // }

// namespace sl
// {
//     template<class T>
//     class vector
//     {
//     public:
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         ~vector()
//         {
//             if(_start)
//             {
//                 delete[] _start;
//                 _start = _finish = _endOfStorage = nullptr;
//             }
//         }

//         //迭代器区间构造
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T>& operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin()const
//         {
//             return _start;
//         }

//         const_iterator end()const
//         {
//             return _finish;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             if(n > capacity())
//             {
//                 size_t sz = size();
//                 T* tmp = new T[n];
//                 for(size_t i = 0; i < sz; i++)
//                 {
//                     tmp[i] = _start[i];
//                 }
//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }
//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }

//             *_finish = x;
//             _finish++;
//         }

//         void display()
//         {
//             iterator it = begin();
//             while(it != end())
//             {
//                 cout << *it << " ";
//                 it++;
//             }
//             cout << endl;
//         }
//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
//     };
// }

// namespace sl
// {
//     template<class T>
//     class vector
//     {
//     public:
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         ~vector()
//         {
//             if(_start)
//             {
//                 delete[] _start;
//                 _start = _finish = _endOfStorage = nullptr;
//             }
//         }

//         //迭代区间构造
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T> operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             size sz = size();
//             if(n > capacity())
//             {
//                 T* tmp = new T[n];
//                 if(_start)
//                 {
//                     for(size_t i = 0; i < sz; i++)
//                     {
//                         tmp[i] = _start[i];
//                     }
//                     delete[] _start;
//                 }
//                 _start = tmp;
//             }
//             _finish = _start + sz;
//             _endOfStorage = _start + n;
//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }

//             *_finish = x;
//             _finish++;
//         }
//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
//     };
// }

// namespace sl
// {
//     template <class T>
//     class vector
//     {
//     public:
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         //迭代器区间构造
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T>& operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin()const
//         {
//             return _start;
//         }

//         const_iterator end()const
//         {
//             return _finish;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             if(n > capacity())
//             {
//                 size_t sz = size();
//                 T* tmp = new T[n];
//                 for(size_t i = 0; i < sz; i++)
//                 {
//                     tmp[i] = _start[i];
//                 }
//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }
//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }
//             *_finish = x;
//             _finish++;
//         }

//         void display()
//         {
//             iterator it = begin();
//             while(it != end())
//             {
//                 cout << *it << " ";
//                 it++;
//             }
//             cout << endl;
//         }

//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
//     };
// }

// namespace sl
// {
//     template<class T>
//     class vector
//     {
//     public:
//         //vector的迭代器本身就是原生指针
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {}

//         ~vector()
//         {
//             if(_start)
//             {
//                 delete[] _start;
//                 _start = _finish = _endOfStorage = nullptr;
//             }
//         }

//         //迭代器区间构造
//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swap(_endOfStorage, v._endOfStorage);
//         }

//         //拷贝构造
//         //vector<T> t2(t1);
//         vector(const vector<T>& v)
//             :_start(nullptr)
//             ,_finish(nullptr)
//             ,_endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         //赋值重载
//         //t1 = t2;
//         vector<T>& operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin()const
//         {
//             return _start;
//         }

//         const_iterator end()const
//         {
//             return _finish;
//         }

//         size_t size()const
//         {
//             return _finish - _start;
//         }

//         size_t capacity()const
//         {
//             return _endOfStorage - _start;
//         }

//         void reserve(size_t n)
//         {
//             if(n > capacity())
//             {
//                 size_t sz = size();
//                 T* tmp = new T[n];
//                 for(size_t i=  0; i < sz; i++)
//                 {
//                     tmp[i] = _start[i];
//                 }
//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }
//         }

//         void push_back(const T& x)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 reserve(capacity() == 0 ? 4 : capacity() * 2);
//             }
//             *_finish = x;
//             ++_finish;
//         }

//         void display()
//         {
//             iterator it = begin();
//             while(it != end())
//             {
//                 cout << *it << " ";
//                 it++;
//             }
//             cout << endl;
//         }

//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
//     };
// }

namespace sl
{
    template <class T>
    class vector
    {
    public:
        typedef T *iterator;
        typedef const T *const_iterator;

        //默认构造函数
        vector()
            : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
        {}

        //注意这里不能使用size_t类型, 因为如果是vector<int> v(10, 2);
        //如果是size_t类型, 则可能调用那个迭代器区间构造(编译器认为更匹配,int,int)
        vector(int n, const T &x = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(n);
            for (int i = 0; i < n; i++)
            {
                push_back(x);
            }
        }

        //析构函数
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endOfStorage = nullptr;
            }
        }

        //迭代器区间构造
        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }

        void swap(vector<T> &v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }

        vector(const vector<T> &v)
            : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
        {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }

        vector<T> &operator=(vector<T> v)
        {
            swap(v);
            return *this;
        }

        size_t size() const
        {
            return _finish - _start;
        }

        size_t capacity() const
        {
            return _endOfStorage - _start;
        }

        //这个函数的实现需要格外注意
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                //注意需要保存元素的个数, 否则_start更新后就不准了
                //因为size() : _finish - _start;
                size_t sz = size();
                T *tmp = new T[n];
                if (_start)
                {
                    //注意不能使用memcpy(), 会导致浅拷贝问题
                    for (size_t i = 0; i < sz; i++)
                    {
                        tmp[i] = _start[i];//这样实现涉及到深浅拷贝也不碍事, 会调用它的深拷贝赋值
                    }
                }

                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }
        }

        void resize(size_t n, const T& val = T())
        {
            if(n > capacity())
            {
                reserve(n);
            }
            if(n > size())
            {
                while(_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }

        void push_back(const T &x)
        {
            if (_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            _finish++;
        }

        void pop_back()
        {
            if(_finish > _start)
            {
                --_finish;
            }
        }

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }

        const T& operator[](size_t pos)const
        {
            assert(pos < size());
            return _start[pos];
        }

        void display()const
        {
            const_iterator it = begin();
            while (it != end())
            {
                cout << *it << " ";
                it++;
            }
            cout << endl;
        }


        void insert(iterator pos, const T& x)
        {
            //检查参数
            assert(pos >= _start && pos <= _finish);

            //扩容
            if(_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }

            iterator end = _finish - 1;
            while(end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = x;
            ++_finish;
        }

    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}

template<class T>
class vector
{
public:
    typedef T* iterator;
    typedef const T* const_iterator;

    // 迭代器相关函数
    iterator begin()
    {
        return _start;
    }

    iterator end()
    {
        return _finish;
    }

    const_iterator cbegin() const
    {
        return _start;
    }

    const_iterator cend() const
    {
        return _finish;
    }

    vector()
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {}

    vector(int n, const T& val = T())
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        reserve(n);

        for(int i = 0; i < n; i++)
        {
            push_back(val);
        }
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        reserve(last - first);

        while(first != last)
        {
            push_back(*first);
            first++;
        }
    }

    void swap(vector<T>& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endOfStorage, v._endOfStorage);
    }

    vector(const vector<T>& v)
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        vector<T> tmp(v.begin(), v.end());
        swap(tmp);
    }

    vector<T>& operator=(vector<T> v)
    {
        swap(v);
        return *this;
    }

    ~vector()
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }

    // 扩容相关函数
    void reserve(size_t n)
    {
        if(n > capacity)
        {
            size_t sz = size();

            T* tmp = new T[n];

            if(_start)
            {
                for(size_t i = 0; i < sz; i++)
                {
                    tmp[i] = _start[i];
                }
            }

            _start = tmp;
            _finish = _start + sz;
            _endOfStorage = _start + n;
        }
    }

    void resize(size_t n, const T& val = T())
    {
        if(n > capacity())
        {
            reserve(n);
        }

        if(n > size())
        {
            while(_finish < _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
        else
        {
            _finish = _start + n;
        }
    }

    // 容器操作函数
    size_t size() const 
    {
        return _finish - _start;
    }

    size_t capacity() const
    {
        return _endOfStorage - _start;
    }

    bool empty() const
    {
        return _start == _finish;
    }

    T& operator[](size_t pos)
    {
        assert(pos < size());
        return _start[pos];
    }

    const T& operator[](size_t pos) const
    {
        assert(pos < size());
        return _start[pos];
    }

    // 尾插 / 尾删
    void push_back(const T& val)
    {
        if(_finish == _endOfStorage)
        {
            size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(newCapacity);
        }

        *_finish = val;
        _finish++;
    }

    void pop_back()
    {
        if(_finish > _start)
            _finish--;
    }

private:
    iterator _start;
    iterator _finish;
    iterator _endOfStorage;
};


// 节点类
template<class T>
struct _list_node
{
    typedef _list_node<T> node;

    T _val;
    node* _prev;
    node* _next;

    _list_node(const T& val = T())
        : _val(val)
        , _prev(nullptr)
        , _next(nullptr)
    {}
};

// 迭代器类
template<class T, class Ref, class Ptr>
struct _list_iterator
{
    typedef _list_node<T> node;
    typedef _list_iterator<T, Ref, Ptr> self;

    node* _node;

    _list_iterator(node* pnode)
        : _node(pnode)
    {}

    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }

    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }

    bool operator==(const self& lt) const
    {
        return _node == lt._node;
    }

    bool operator!=(const self& lt) const
    {
        return _node != lt._node;
    }

    Ref operator*()
    {
        return _node->_val;
    }

    Ptr operator->()
    {
        return &_node->_val;
    }
};

// List类
template<class T> 
class List
{
public:
    typedef _list_node<T> node;
    typedef _list_iterator<T, T&, T*> iterator;
    typedef _list_iterator<const T, const T&, const T*> const_iterator;

    node* _head;

    List()
    {
        _head = new node();
        _head->_prev = _head;
        _head->_next = _head;
    }

    void head_init()
    {
        _head = new node();
        _head->_prev = _head;
        _head->_next = _head;
    }

    // 迭代器区间构造
    template<class InputIterator>
    List(InputIterator first, InputIterator last)
    {
        head_init();

        while(first != last)
        {
            push_back(*first);
            first++;
        }
    }

    // List(const List<T>& lt)
    // {
    //     head_init();

    //     for(const auto& e : lt)
    //     {
    //         push_back(e);
    //     }
    // }


    void swap(List<T>& lt)
    {
        std::swap(_head, lt._head);
    }

    List(const List<T>& lt)
    {
        head_init();

        List<T> tmp(lt.begin(), lt.end());
        swap(tmp);
    }

    // List<T>& operator=(const List<T>& lt)
    // {
    //     if(this != &lt)
    //     {
    //         clear();

    //         for(const auto& e : lt)
    //         {
    //             push_back(e);
    //         }
    //     }

    //     return *this;
    // }

    List<T>& operator=(List<T> lt)
    {
        swap(lt);
        return *this;
    }

    ~List()
    {
        clear();

        delete _head;
        _head = nullptr;
    }

    // 迭代器相关函数
    iterator begin()
    {
        return iterator(_head->_next);
    }

    iterator end()
    {
        return iterator(_head);
    }

    const_iterator begin() const
    {
        return const_iterator(_head->_next);
    }

    const_iterator end() const
    {
        return const_iterator(_head);
    }

    // 容器相关函数
    void clear()
    {
        iterator it = begin();

        while(it != end())
        {
            it = erase(it);
        }
    }

    T& front()
    {
        return *begin();
    }

    T& back()
    {
        return *(--end());
    }

    const T& front() const
    {
        return *begin();
    }

    const T& back() const
    {
        return *(--end());
    }


    // 随机插入 / 删除函数
    void insert(iterator pos, const T& val)
    {
        assert(pos->_node);

        node* newnode = new node(val);

        node* cur = pos->_node;
        node* prev = cur->_prev;
        
        newnode->_next = cur;
        cur->_prev = newnode;

        newnode->_prev = prev;
        prev->_next = newnode;
    }

    iterator erase(iterator pos)
    {
        assert(pos->_node);
        assert(pos != end());

        node* cur = pos->_node;
        node* prev = cur->_prev;
        node* next = cur->_next;

        delete cur;

        prev->_next = next;
        next->_prev = prev;

        return iterator(next);
    }

    void push_back(const T& val)
    {
        insert(end(), val);
    }

};



template<class T>
class vector
{
public:
    // vector的迭代器就是一个原生指针
    typedef T* iterator;
    typedef const T*  const_iterator;

    vector()
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {}

    vector(int n, const T& val = T())
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        reserve(n);

        for(int i = 0; i < n; i++)
        {
            push_back(val);
        }
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        reserve(last - first);

        while(first != last)
        {
            push_back(*first);
            first++;
        }
    }

    void swap(vector<T> v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endOfStorage, v._endOfStorage);
    }

    vector(const vector<T>& v)
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        vector<T> tmp(v.begin(), v.end());
        swap(tmp);
    }

    vector<T>& operator=(vector<T> v)
    {
        swap(v);
        return *this;
    }

    ~vector()
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }


    // 迭代器相关函数
    iterator begin()
    {
        return _start;
    }

    iterator end()
    {
        return _finish;
    }

    const_iterator begin() const
    {
        return _start;
    }

    const_iterator end() const
    {
        return _finish;
    }

    // 容器操作函数
    size_t size() const
    {
        return _finish - _start;
    }

    size_t capacity() const
    {
        return _endOfStorage - _start;
    }

    bool empty() const
    {
        return _start == _finish;
    }

    T& operator[](size_t pos)
    {
        assert(pos < size());

        return _start[pos];
    }

    const T& operator[](size_t pos) const
    {
        assert(pos < size());

        return _start[pos];
    }

    // 扩容相关函数
    void reserve(size_t n)
    {
        if(n > capacity())
        {
            size_t sz = size();

            T* tmp = new T[n];

            if(_start)
            {
                for(size_t i = 0; i < sz; i++)
                {
                    tmp[i] = _start[i];
                }
            }

            _start = tmp;
            _finish = _start + sz;
            _endOfStorage = _start + n;
        }
    }

    void resize(size_t n, const T& val = T())
    {
        if(n > capacity())
        {
            reserve(n);
        }

        if(n > size())
        {
            while(_finish < _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
        else
        {
            _finish = _start + n;
        }
    }

    // 尾插 / 尾删
    void push_back(const T& val)
    {
        if(_finish == _endOfStorage)
        {
            size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(newCapacity);
        }

        *_finish = val;
        _finish++;
    }

    void pop_back()
    {
        if(_finish > _start)
        {
            _finish--;
        }
    }

private:
    iterator _start;
    iterator _finish;
    iterator _endOfStorage;
};


template<class T>
class vector
{
public:
    // vector的迭代器就是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;

    vector()
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {}

    vector(int n, const T& val = ())
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        reserve(n);

        for(int i = 0; i < n; i++)
        {
            push_back(val);
        }
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        reserve(last - first);

        while(first != last)
        {
            push_back(*first);
            first++;
        }
    }

    void swap(vector<T>& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endOfStorage, v._endOfStorage);
    }

    vector(const vector<T>& v)
        : _start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        vector<T> tmp(v.begin(), v.end());
        swap(tmp);
    }

    vector<T>& operator=(vector<T> v)
    {
        swap(v);
        return *this;
    }

    ~vector()
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }

    // 迭代器相关函数
    iterator begin()
    {
        return _start;
    }

    iterator end()
    {
        return _finish;
    }

    const_iterator begin() const
    {
        return _start;
    }

    const_iterator end() const
    {
        return _finish;
    }

    // 容器操作函数
    size_t size() const
    {
        return _finish - _start;
    }

    size_t capacity() const
    {
        return _endOfStorage - _start;
    }

    bool empty() const
    {
        return _start == _finish;
    }

    T& operator[](size_t pos)
    {
        assert(pos < size());

        return _start[pos];
    }

    const T& operator[](size_t pos) const
    {
        assert(pos < size());

        return _start[pos];
    }

    // 扩容相关函数
    void reserve(size_t n)
    {
        if(n > capacity())
        {
            size_t sz = size();

            T* tmp = new T[n];

            if(_start)
            {
                for(size_t i = 0; i < sz; i++)
                {
                    tmp[i] = _start[i];
                }
            }

            _start = tmp;
            _finish = _start + sz;
            _endOfStorage = _start + n;
        }
    }

    void resize(size_t n, const T& val = T())
    {
        if(n > capacity())
        {
            reserve(n);
        }

        if(n > size())
        {
            while(_finish < _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
        else
        {
            _finish = _start + n;
        }
    }

    // 尾插 / 尾删
    void push_back(const T& val)
    {
        if(_finish == _endOfStorage)
        {
            size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(newCapacity);
        }

        *_finish = val;
        _finish++;
    }

    void pop_back()
    {
        if(_finish > _start)
        {
            _finish--;
        }
    }

private:
    iterator _start;
    iterator _finish;
    iterator _endOfStorage;
};



// {
//     template<class T>
//     class vector
//     {
//     // vector的迭代器本质上是一个原生指针
//     public:
//         typedef T* iterator;
//         typedef const T* const_iterator;

//         vector()
//             : _start(nullptr)
//             , _finish(nullptr)
//             , _endOfStorage(nullptr)
//         {}

//         vector(int n, const T& val = T())
//             : _start(nullptr)
//             , _finish(nullptr)
//             , _endOfStorage(nullptr)
//         {
//             reserve(n);

//             for(int i = 0; i < n; i++)
//             {
//                 push_back(val);
//             }
//         }

//         template<class InputIterator>
//         vector(InputIterator first, InputIterator last)
//             : _start(nullptr)
//             , _finish(nullptr)
//             , _endOfStorage(nullptr)
//         {
//             reserve(last - first);

//             while(first != last)
//             {
//                 push_back(*first);
//                 first++;
//             }
//         }

//         void swap(vector<T>& v)
//         {
//             std::swap(_start, v._start);
//             std::swap(_finish, v._finish);
//             std::swao(_endOfStorage, v._endOfStorage);
//         }

//         vector(const vector<T>& v)
//             : _start(nullptr)
//             , _finish(nullptr)
//             , _endOfStorage(nullptr)
//         {
//             vector<T> tmp(v.begin(), v.end());
//             swap(tmp);
//         }

//         vector<T>& operator=(vector<T> v)
//         {
//             swap(v);
//             return *this;
//         }

//         ~vector()
//         {
//             delete[] _start;
//             _start = _finish = _endOfStorage = nullptr;
//         }

//         // 迭代器相关函数
//         iterator begin()
//         {
//             return _start;
//         }

//         iterator end()
//         {
//             return _finish;
//         }

//         const_iterator begin() const
//         {
//             return _start;
//         }

//         const_iterator end() const
//         {
//             return _finish;
//         }

//         // 容器操作函数
//         size_t size() const
//         {
//             return _finish - _start;
//         }

//         size_t capacity() const
//         {
//             return _endOfStorage - _start;
//         }

//         bool empty() const
//         {
//             return _start == _finish;
//         }

//         T& operator[](size_t pos)
//         {
//             assert(pos < size());

//             return _start[pos];
//         }

//         const T& operator[](size_t pos)
//         {
//             assert(pos < size());

//             return _start[pos];
//         }

//         // 扩容相关函数
//         void reserve(size_t n)
//         {
//             if(n > capacity())
//             {
//                 size_t sz = size();

//                 T* tmp = new T[n];

//                 if(_start)
//                 {
//                     for(size_t i = 0; i < sz; i++)
//                     {
//                         tmp[i] = _start[i];
//                     }
//                 }

//                 _start = tmp;
//                 _finish = _start + sz;
//                 _endOfStorage = _start + n;
//             }
//         }

//         void resize(size_t n, const T& val = T())
//         {
//             if(n > capacity())
//             {
//                 reserve(n);
//             }

//             if(n > size())
//             {
//                 while(_finish < _start + n)
//                 {
//                     *_finish = val;
//                     _finish++;
//                 }
//             }
//             else
//             {
//                 _finish = _start + n;
//             }
//         }

//         // 尾插 / 尾删
//         void push_back(const T& val)
//         {
//             if(_finish == _endOfStorage)
//             {
//                 size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
//                 reserve(newCapacity);
//             }

//             *_finish = val;
//             _finish++;
//         }

//         void pop_back()
//         {
//             if(_finish > _start)
//             {
//                 _finish--;
//             }
//         }


//     private:
//         iterator _start;
//         iterator _finish;
//         iterator _endOfStorage;
//     };
// }




namespace sl
{
    template<class T>
    class vector
    {
    public:
        // vector的迭代器本质上就是原生指针
        typedef T* iterator;
        typedef const T* const_iterator;


        vector()
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {}


        vector(int n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(n);

            for(int i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(last - first);

            while(first != last)
            {
                push_back(*first);
                first++;
            }
        }

        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }

        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }

        vector<T>& operator=(vector<T> v)
        {
            swap(v);

            return *this;
        }

        ~vector()
        {
            if(_start)
            {
                delete[] _start;
                _start = _finish = _endOfStorage = nullptr;
            }
        }

        // 迭代器相关函数
        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        // 容器操作函数
        size_t size() const
        {
            return _finish - _start;
        }

        size_t capacity() const
        {
            return _endOfStorage - _start;
        }

        bool empty() const
        {
            return _start == _finish;
        }

        T& operator[](size_t pos)
        {
            assert(pos < size());

            return _start[pos];
        }

        const T& operator[](size_t pos) const
        {
            assert(pos < size());

            return _start[pos];
        }

        // 扩容相关函数
        void reserve(size_t n)
        {
            if(n > capacity())
            {
                size_t sz = size();

                T* tmp = new T[n];

                if(_start)
                {
                    for(size_t i = 0; i < sz; i++)
                    {
                        tmp[i] = _start[i];
                    }
                }
            }

            _start = tmp;
            _finish = _start + sz;
            _endOfStorage = _start + n;
        }

        void resize(size_t n, const T& val = T())
        {
            if(n > capacity())
            {
                reserve(n);
            }

            if(n > size())
            {
                while(_finish < _start + n)
                {
                    *_finish = val;
                    _finish++;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }

        // 尾插 / 尾删
        void push_back(const T& val)
        {
            if(_finish == _endOfStorage)
            {
                size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newCapacity);
            }

            *_finish = val;
            _finish++;
        }

        void pop_back()
        {
            if(_finish > _start)
            {
                _finish--;
            }
        }



    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}



namespace sl
{
    template<class T>
    class vector
    {
    public:
        // vector的迭代器本质上就是原生指针
        typedef T* iterator;
        typedef const T* const_iterator;

        vector()
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {}

        vector(int n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            for(int i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            while(first != last)
            {
                psuh_back(*first);
                first++;
            }
        }

        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }

        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }

        vector<T>& operator=(vector<T> v)
        {
            swap(v);

            return *this;
        }

        ~vector()
        {
            if(_start)
            {
                delete[] _start;
                _start = _finish = _endOfStorage = nullptr;
            }
        }

        // 迭代器相关函数
        iterator begin()
        {
            return _start;
        }

        iterator end() 
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        // 容器操作函数
        size_t size() const
        {
            return _finish - _start;
        }

        size_t capacity() const
        {
            return _endOfStorage - _start;
        }

        bool empty() const
        {
            return _start == _finish;
        }

        T& operator[](size_t pos)
        {
            assert(pos < size());

            return _start[pos];
        }

        const T& operator[](size_t pos) const
        {
            assert(pos < size());

            return _start[pos];
        }

        // 扩容相关函数
        void reserve(size_t n)
        {
            if(n > capacity())
            {
                size_t sz = size();

                T* tmp = new T[n];

                if(_start)
                {
                    for(size_t i = 0; i < sz; i++)
                    {
                        tmp[i] = _start[i];
                    }
                }

                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }
        }


        void resize(size_t n, const T& val = T())
        {
            if(n > capacity())
            {
                reserve(n);
            }

            if(n > size())
            {
                while(finish < _start + n)
                {
                    *_finish = val;
                    _finish++;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }

        // 尾插 / 尾删
        void push_back(const T& val)
        {
            if(_finish == _endOfStorage)
            {
                size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newCapacity);
            }

            *_finish = val;
            _finish++;
        }

        void pop_back()
        {
            if(_finish > _start)
            {
                _finish--;
            }
        }
    
        
    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}




namespace sl
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;


        vector()
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {}


        vector(int n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            for(int i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            while(first != last)
            {
                push_back(*first);
                first++;
            }
        }

        void swap(vector<T> v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }


        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            vector<T> tmp(v.begin(), v.end());

            swap(tmp);
        }

        vector<T>& operator=(vector<T> v)
        {
            swap(v);

            return *this;
        }


        ~vector()
        {
            if(_start)
            {
                delete[] _start;
                _start = _finish = _endOfStorage = nullptr;
            }
        }


        // 迭代器相关函数
        iterator begin()
        {
            return start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        // 容器操作函数
        T& operator[](size_t pos)
        {
            assert(pos < size());

            return _start[pos];
        }

        const T& operator[](size_t pos) const
        {
            assert(pos < size());

            return _start[pos];
        }

        size_t size() const
        {
            return _finish - _start;
        }

        size_t capacity() const
        {
            return _endOfStorage - _start;
        }

        bool empty() const
        {
            return _start == _finish;
        }

        // 扩容相关函数
        void reserve(size_t n)
        {
            if(n > capacity())
            {
                size_t sz = size();
                T* tmp = new T[n];

                if(_start)
                {
                    for(size_t i = 0; i < sz; i++)
                    {
                        tmp[i] = _start[i];
                    }
                }

                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }
        }

        void resize(size_t n, const T& val = T())
        {
            if(n > capacity())
                reserve(n);
            
            if(n > size())
            {
                while(_finish < _start + n)
                {
                    *_finish = val;
                    _finish++;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }


        void push_back(const T& val)
        {
            if(_finish == _endOfStorage)
            {
                size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newCapacity);

                *_finish = val;
                _finish++;
            }
        }

    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}




